package com.qjc.demo.train.greedy;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @ClassName: BagDemo1
 * @Description: 贪心算法-部分背包
 * 时间复杂度是O(n)
 * 优点：性能高，能用贪心算法解决的往往是最优解
 * 缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的
 * 在实际情况下，用贪心算法解决问题的思路，并不总能给出最优解
 * @Author: qjc
 * @Date: 2022/5/3 12:10 AM
 */
public class BagDemo1 {

    double maxWeight;// 背包装的最大重量

    public void take(Goods[] goodsList) {
        // 先对物品按照单价排序
        Goods[] sortGoodsList = sort(goodsList);
        // 当前总重量
        double sum_w = 0;
        for (Goods goods : sortGoodsList) {
            sum_w += goods.weight;
            if (sum_w <= maxWeight) {
                System.out.println(goods.name + "取" + goods.weight + "kg");
            } else {
                System.out.println(goods.name + "取" + (maxWeight - (sum_w - goods.weight)) + "kg");
                return;
            }
        }
    }

    private Goods[] sort(Goods[] goodsList) {
        // 按照单价倒序排列
        List<Goods> goods = Arrays.asList(goodsList);
        Collections.sort(goods, (v1, v2) -> {
            if (v1.unitPrice < v2.unitPrice)
                return 1;
            else
                return -1;
        });
        return goods.toArray(goodsList);
    }

    public static void main(String[] args) {
        BagDemo1 bagDemo1 = new BagDemo1();
        bagDemo1.maxWeight = 50;

        Goods aGoods = new Goods("A", 10, 60);
        Goods bGoods = new Goods("B", 20, 100);
        Goods cGoods = new Goods("C", 30, 120);

        Goods[] goodsList = {bGoods, aGoods, cGoods};
        bagDemo1.take(goodsList);

    }

}
